<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html lang="en">

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  <title>LCOV - gcov.info - curves/Sorter.cpp</title>
  <link rel="stylesheet" type="text/css" href="../gcov.css">
</head>

<body>

  <table width="100%" border=0 cellspacing=0 cellpadding=0>
    <tr><td class="title">LCOV - code coverage report</td></tr>
    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>

    <tr>
      <td width="100%">
        <table cellpadding=1 border=0 width="100%">
          <tr>
            <td width="10%" class="headerItem">Current view:</td>
            <td width="35%" class="headerValue"><a href="../index.html">top level</a> - <a href="index.html">curves</a> - Sorter.cpp<span style="font-size: 80%;"> (source / <a href="Sorter.cpp.func-sort-c.html">functions</a>)</span></td>
            <td width="5%"></td>
            <td width="15%"></td>
            <td width="10%" class="headerCovTableHead">Hit</td>
            <td width="10%" class="headerCovTableHead">Total</td>
            <td width="15%" class="headerCovTableHead">Coverage</td>
          </tr>
          <tr>
            <td class="headerItem">Test:</td>
            <td class="headerValue">gcov.info</td>
            <td></td>
            <td class="headerItem">Lines:</td>
            <td class="headerCovTableEntry">111</td>
            <td class="headerCovTableEntry">115</td>
            <td class="headerCovTableEntryHi">96.5 %</td>
          </tr>
          <tr>
            <td class="headerItem">Date:</td>
            <td class="headerValue">2014-06-30 01:17:31</td>
            <td></td>
            <td class="headerItem">Functions:</td>
            <td class="headerCovTableEntry">11</td>
            <td class="headerCovTableEntry">11</td>
            <td class="headerCovTableEntryHi">100.0 %</td>
          </tr>
          <tr><td><img src="../glass.png" width=3 height=3 alt=""></td></tr>
        </table>
      </td>
    </tr>

    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>
  </table>

  <table cellpadding=0 cellspacing=0 border=0>
    <tr>
      <td><br></td>
    </tr>
    <tr>
      <td>
<pre class="sourceHeading">          Line data    Source code</pre>
<pre class="source">
<a name="1"><span class="lineNum">       1 </span>            : /* </a>
<span class="lineNum">       2 </span>            :  * File:   Sorter.cpp
<span class="lineNum">       3 </span>            :  * Author: nichole
<span class="lineNum">       4 </span>            :  * 
<span class="lineNum">       5 </span>            :  * Created on April 27, 2014
<span class="lineNum">       6 </span>            :  */
<span class="lineNum">       7 </span>            : 
<span class="lineNum">       8 </span>            : #include &quot;Sorter.h&quot;
<span class="lineNum">       9 </span>            : 
<a name="10"><span class="lineNum">      10 </span>            : namespace gev {</a>
<span class="lineNum">      11 </span>            :     
<span class="lineNum">      12 </span><span class="lineCov">          7 :     Sorter::Sorter() {</span>
<a name="13"><span class="lineNum">      13 </span><span class="lineCov">         14 :     }</span></a>
<span class="lineNum">      14 </span>            :     
<span class="lineNum">      15 </span><span class="lineCov">         21 :     Sorter::~Sorter() {</span>
<span class="lineNum">      16 </span><span class="lineCov">         21 :     }</span>
<a name="17"><span class="lineNum">      17 </span>            :     </a>
<span class="lineNum">      18 </span>            :     // use quicksort to sort in place at avg runtime cost of O(N lg2 (N))
<span class="lineNum">      19 </span><span class="lineCov">          4 :     void Sorter::sort(vector&lt;uint32_t&gt;&amp; a, vector&lt;uint32_t&gt;&amp; b) {</span>
<span class="lineNum">      20 </span><span class="lineCov">          4 :         if (a.empty()) {</span>
<span class="lineNum">      21 </span><span class="lineNoCov">          0 :             return;</span>
<span class="lineNum">      22 </span>            :         }
<span class="lineNum">      23 </span><span class="lineCov">          4 :         if (a.size() != b.size()) {</span>
<span class="lineNum">      24 </span><span class="lineNoCov">          0 :             return;</span>
<span class="lineNum">      25 </span>            :         }
<span class="lineNum">      26 </span><span class="lineCov">          4 :         _sort(a, b, 0, a.size() - 1);</span>
<a name="27"><span class="lineNum">      27 </span><span class="lineCov">          8 :     }</span></a>
<span class="lineNum">      28 </span>            :     
<span class="lineNum">      29 </span><span class="lineCov">     745946 :     void Sorter::_sort(vector&lt;uint32_t&gt;&amp; a, vector&lt;uint32_t&gt;&amp; b, long idxLo, </span>
<span class="lineNum">      30 </span><span class="lineCov">     745946 :         long idxHi) {</span>
<span class="lineNum">      31 </span>            :         
<span class="lineNum">      32 </span><span class="lineCov">     745946 :         if (idxLo &lt; idxHi) {</span>
<span class="lineNum">      33 </span><span class="lineCov">     372971 :             long idxMid = _partition(a, b, idxLo, idxHi);</span>
<span class="lineNum">      34 </span><span class="lineCov">     372971 :             _sort(a, b, idxLo, idxMid - 1);</span>
<span class="lineNum">      35 </span><span class="lineCov">     372971 :             _sort(a, b, idxMid + 1, idxHi);</span>
<span class="lineNum">      36 </span><span class="lineCov">     372971 :         }</span>
<a name="37"><span class="lineNum">      37 </span><span class="lineCov">     745946 :     }</span></a>
<span class="lineNum">      38 </span>            :     
<span class="lineNum">      39 </span><span class="lineCov">     372971 :     long Sorter::_partition(vector&lt;uint32_t&gt;&amp; a, vector&lt;uint32_t&gt;&amp; b, </span>
<span class="lineNum">      40 </span><span class="lineCov">     372971 :         long idxLo, long idxHi) {</span>
<span class="lineNum">      41 </span>            :                 
<span class="lineNum">      42 </span><span class="lineCov">     372971 :         uint32_t x = a[idxHi];</span>
<span class="lineNum">      43 </span><span class="lineCov">     372971 :         long store = idxLo - 1;</span>
<span class="lineNum">      44 </span>            :  
<span class="lineNum">      45 </span><span class="lineCov">57345708286 :         for (long i = idxLo; i &lt; idxHi; i++) {</span>
<span class="lineNum">      46 </span><span class="lineCov">28672481172 :             if (a[i] &gt; x) {</span>
<span class="lineNum">      47 </span><span class="lineCov">    2177129 :                 store++;</span>
<span class="lineNum">      48 </span><span class="lineCov">    2177129 :                 if (i != store) {</span>
<span class="lineNum">      49 </span><span class="lineCov">    1976326 :                     long swap = a[i];</span>
<span class="lineNum">      50 </span><span class="lineCov">    1976326 :                     a[i] = a[store];</span>
<span class="lineNum">      51 </span><span class="lineCov">    1976326 :                     a[store] = swap;</span>
<span class="lineNum">      52 </span>            : 
<span class="lineNum">      53 </span><span class="lineCov">    1976326 :                     swap = b[i];</span>
<span class="lineNum">      54 </span><span class="lineCov">    1976326 :                     b[i] = b[store];</span>
<span class="lineNum">      55 </span><span class="lineCov">    1976326 :                     b[store] = swap;</span>
<span class="lineNum">      56 </span><span class="lineCov">    1976326 :                 }</span>
<span class="lineNum">      57 </span><span class="lineCov">    2177129 :             }</span>
<span class="lineNum">      58 </span><span class="lineCov">28672481172 :         }</span>
<span class="lineNum">      59 </span>            : 
<span class="lineNum">      60 </span><span class="lineCov">     372971 :         store++;</span>
<span class="lineNum">      61 </span><span class="lineCov">     372971 :         long swap = a[store];</span>
<span class="lineNum">      62 </span><span class="lineCov">     372971 :         a[store] = a[idxHi];</span>
<span class="lineNum">      63 </span><span class="lineCov">     372971 :         a[idxHi] = swap;</span>
<span class="lineNum">      64 </span>            : 
<span class="lineNum">      65 </span><span class="lineCov">     372971 :         swap = b[store];</span>
<span class="lineNum">      66 </span><span class="lineCov">     372971 :         b[store] = b[idxHi];</span>
<span class="lineNum">      67 </span><span class="lineCov">     372971 :         b[idxHi] = swap;</span>
<span class="lineNum">      68 </span>            :         
<span class="lineNum">      69 </span><span class="lineCov">     372971 :         return store;</span>
<span class="lineNum">      70 </span>            :     }
<a name="71"><span class="lineNum">      71 </span>            :     </a>
<span class="lineNum">      72 </span>            :     //=========
<span class="lineNum">      73 </span><span class="lineCov">          3 :     void Sorter::sort(float* a, float* b, float* c, long length) {</span>
<span class="lineNum">      74 </span><span class="lineCov">          3 :         if (a == NULL) {</span>
<span class="lineNum">      75 </span><span class="lineNoCov">          0 :             return;</span>
<span class="lineNum">      76 </span>            :         }
<span class="lineNum">      77 </span><span class="lineCov">          3 :         if (length == 0) {</span>
<span class="lineNum">      78 </span><span class="lineNoCov">          0 :             return;</span>
<span class="lineNum">      79 </span>            :         }
<span class="lineNum">      80 </span><span class="lineCov">          3 :         _sort(a, b, c, 0, length - 1);</span>
<a name="81"><span class="lineNum">      81 </span><span class="lineCov">          6 :     }</span></a>
<span class="lineNum">      82 </span>            :     
<span class="lineNum">      83 </span><span class="lineCov">       2859 :     void Sorter::_sort(float* a, float* b, float* c, long idxLo, long idxHi) {</span>
<span class="lineNum">      84 </span>            :         
<span class="lineNum">      85 </span><span class="lineCov">       2859 :         int q = -1;</span>
<span class="lineNum">      86 </span>            :         
<span class="lineNum">      87 </span><span class="lineCov">       2859 :         if (idxLo &lt; idxHi) {</span>
<span class="lineNum">      88 </span><span class="lineCov">       1428 :             q = (idxLo + idxHi)/2;</span>
<span class="lineNum">      89 </span><span class="lineCov">       1428 :             _sort(a, b, c, idxLo, q);</span>
<span class="lineNum">      90 </span><span class="lineCov">       1428 :             _sort(a, b, c, q + 1, idxHi);</span>
<span class="lineNum">      91 </span><span class="lineCov">       1428 :             _merge(a, b, c, idxLo, q, idxHi);</span>
<span class="lineNum">      92 </span><span class="lineCov">       1428 :         }</span>
<a name="93"><span class="lineNum">      93 </span><span class="lineCov">       2859 :     }</span></a>
<span class="lineNum">      94 </span>            :     
<span class="lineNum">      95 </span><span class="lineCov">       1428 :     void Sorter::_merge(float* a, float* b, float* c, long idxLo, long idxMid,</span>
<span class="lineNum">      96 </span><span class="lineCov">       1428 :         long idxHi) {</span>
<span class="lineNum">      97 </span>            :                 
<span class="lineNum">      98 </span><span class="lineCov">       1428 :         long nLeft = idxMid + 2 - idxLo;</span>
<span class="lineNum">      99 </span><span class="lineCov">       1428 :         long nRight =  idxHi + 2 - (idxMid + 1);</span>
<span class="lineNum">     100 </span><span class="lineCov">       1428 :         size_t leftSz = nLeft * sizeof(float);</span>
<span class="lineNum">     101 </span><span class="lineCov">       1428 :         size_t rightSz = nRight * sizeof(float);</span>
<span class="lineNum">     102 </span><span class="lineCov">       1428 :         size_t leftSz0 = (nLeft - 1 ) * sizeof(float);</span>
<span class="lineNum">     103 </span><span class="lineCov">       1428 :         size_t rightSz0 = (nRight - 1) * sizeof(float);</span>
<span class="lineNum">     104 </span>            :         
<span class="lineNum">     105 </span><span class="lineCov">       1428 :         float* leftA = (float *)malloc(leftSz);</span>
<span class="lineNum">     106 </span><span class="lineCov">       1428 :         float* leftB = (float *)malloc(leftSz);</span>
<span class="lineNum">     107 </span><span class="lineCov">       1428 :         float* leftC = (float *)malloc(leftSz);</span>
<span class="lineNum">     108 </span>            :         
<span class="lineNum">     109 </span><span class="lineCov">       1428 :         memcpy(leftA, a + idxLo, leftSz0);</span>
<span class="lineNum">     110 </span><span class="lineCov">       1428 :         memcpy(leftB, b + idxLo, leftSz0);        </span>
<span class="lineNum">     111 </span><span class="lineCov">       1428 :         memcpy(leftC, c + idxLo, leftSz0);</span>
<span class="lineNum">     112 </span>            :         
<span class="lineNum">     113 </span><span class="lineCov">       1428 :         float* rightA = (float *)malloc(rightSz);        </span>
<span class="lineNum">     114 </span><span class="lineCov">       1428 :         float* rightB = (float *)malloc(rightSz);</span>
<span class="lineNum">     115 </span><span class="lineCov">       1428 :         float* rightC = (float *)malloc(rightSz);</span>
<span class="lineNum">     116 </span>            :         
<span class="lineNum">     117 </span><span class="lineCov">       1428 :         memcpy(rightA, a + (idxMid + 1), rightSz0);</span>
<span class="lineNum">     118 </span><span class="lineCov">       1428 :         memcpy(rightB, b + (idxMid + 1), rightSz0);        </span>
<span class="lineNum">     119 </span><span class="lineCov">       1428 :         memcpy(rightC, c + (idxMid + 1), rightSz0);</span>
<span class="lineNum">     120 </span>            :         
<span class="lineNum">     121 </span><span class="lineCov">       1428 :         float sentinel = FLT_MAX;</span>
<span class="lineNum">     122 </span><span class="lineCov">       1428 :         leftA[nLeft - 1] = sentinel;</span>
<span class="lineNum">     123 </span><span class="lineCov">       1428 :         leftB[nLeft - 1] = sentinel;</span>
<span class="lineNum">     124 </span><span class="lineCov">       1428 :         leftC[nLeft - 1] = sentinel;</span>
<span class="lineNum">     125 </span><span class="lineCov">       1428 :         rightA[nRight - 1] = sentinel;</span>
<span class="lineNum">     126 </span><span class="lineCov">       1428 :         rightB[nRight - 1] = sentinel;</span>
<span class="lineNum">     127 </span><span class="lineCov">       1428 :         rightC[nRight - 1] = sentinel;</span>
<span class="lineNum">     128 </span>            :         
<span class="lineNum">     129 </span><span class="lineCov">       1428 :         long leftPos = 0;</span>
<span class="lineNum">     130 </span><span class="lineCov">       1428 :         long rightPos = 0;</span>
<span class="lineNum">     131 </span>            :         
<span class="lineNum">     132 </span>            :         //sort by a, then if equal b, then if equal c
<span class="lineNum">     133 </span>            :         
<span class="lineNum">     134 </span><span class="lineCov">      32930 :         for (int k = idxLo; k &lt;= idxHi; k++) {</span>
<span class="lineNum">     135 </span>            :             
<span class="lineNum">     136 </span><span class="lineCov">      15037 :             bool assignToLeft = (leftA[leftPos] &lt; rightA[rightPos]);</span>
<span class="lineNum">     137 </span>            :             
<span class="lineNum">     138 </span><span class="lineCov">      26412 :             if (!assignToLeft &amp;&amp; (leftA[leftPos] == rightA[rightPos])) {</span>
<span class="lineNum">     139 </span>            :                 
<span class="lineNum">     140 </span><span class="lineCov">       5694 :                 assignToLeft = (leftB[leftPos] &lt; rightB[rightPos]);</span>
<span class="lineNum">     141 </span>            : 
<span class="lineNum">     142 </span><span class="lineCov">       8603 :                 if (!assignToLeft &amp;&amp; (leftB[leftPos] == rightB[rightPos])) {</span>
<span class="lineNum">     143 </span>            :                     
<span class="lineNum">     144 </span><span class="lineCov">       1545 :                     assignToLeft = (leftC[leftPos] &lt;= rightC[rightPos]);</span>
<span class="lineNum">     145 </span><span class="lineCov">       1545 :                 }                </span>
<span class="lineNum">     146 </span><span class="lineCov">       5694 :             }</span>
<span class="lineNum">     147 </span>            :             
<span class="lineNum">     148 </span><span class="lineCov">      15037 :             if (assignToLeft) {</span>
<span class="lineNum">     149 </span><span class="lineCov">       7857 :                 a[k] = leftA[leftPos];</span>
<span class="lineNum">     150 </span><span class="lineCov">       7857 :                 b[k] = leftB[leftPos];</span>
<span class="lineNum">     151 </span><span class="lineCov">       7857 :                 c[k] = leftC[leftPos];</span>
<span class="lineNum">     152 </span><span class="lineCov">       7857 :                 leftPos++;</span>
<span class="lineNum">     153 </span><span class="lineCov">       7857 :             } else {</span>
<span class="lineNum">     154 </span><span class="lineCov">       7180 :                 a[k] = rightA[rightPos];</span>
<span class="lineNum">     155 </span><span class="lineCov">       7180 :                 b[k] = rightB[rightPos];</span>
<span class="lineNum">     156 </span><span class="lineCov">       7180 :                 c[k] = rightC[rightPos];</span>
<span class="lineNum">     157 </span><span class="lineCov">       7180 :                 rightPos++;</span>
<span class="lineNum">     158 </span>            :             }   
<span class="lineNum">     159 </span><span class="lineCov">      15037 :         }</span>
<span class="lineNum">     160 </span>            :         
<span class="lineNum">     161 </span><span class="lineCov">       1428 :         free(leftA);</span>
<span class="lineNum">     162 </span><span class="lineCov">       1428 :         free(leftB);</span>
<span class="lineNum">     163 </span><span class="lineCov">       1428 :         free(leftC);</span>
<span class="lineNum">     164 </span><span class="lineCov">       1428 :         free(rightA);</span>
<span class="lineNum">     165 </span><span class="lineCov">       1428 :         free(rightB);</span>
<span class="lineNum">     166 </span><span class="lineCov">       1428 :         free(rightC);</span>
<span class="lineNum">     167 </span><span class="lineCov">       1428 :     }</span>
<span class="lineNum">     168 </span>            :     
<span class="lineNum">     169 </span>            : } // end namespace
</pre>
      </td>
    </tr>
  </table>
  <br>

  <table width="100%" border=0 cellspacing=0 cellpadding=0>
    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>
    <tr><td class="versionInfo">Generated by: <a href="http://ltp.sourceforge.net/coverage/lcov.php" target="_parent">LCOV version 1.11</a></td></tr>
  </table>
  <br>

</body>
</html>
